Graph-based electronic modeling is used, for example, in the field of system reliability analysis. Many methods currently exist for calculating system risk in the form of likelihood of failure. Within this field, there are specific references to the use of “cut-sets” to enable fast enumeration of Binary Decision Diagrams (BDDs) for Probabilistic Risk Assessment (PRA).
In the field of communication network security analysis, there are cases where cut-sets have been used as a method for identifying critical points in a network graph where network attacks or intrusions could be detected. One such approach is described in Kodialam and Lakshman, “Detecting Network Intrusions via Sampling: A Game Theoretic Approach”, IEEE, IEEE INFOCOM 2003, San Francisco, Calif., USA, Mar. 30-Apr. 3, 2003. In that paper, cut-sets are used to identify key points in a network for flow monitoring between a source endpoint and a destination endpoint.
Currently known applications of cut-sets tend to focus on algorithms for initial enumeration or computation of the cut-sets. No mechanisms are provided for handling re-enumeration of cut-sets due to changes in the topology of an underlying graph.
Thus, one potential problem with known graph-based modeling techniques lies in the re-enumeration of cut-sets, between source and destination endpoints for instance, following a change in a graph-based model. It appears as though currently known techniques involve completely re-enumerating all cut-sets in the event of any topology change in an underlying graph. This is very inefficient, and can be particularly problematic for cut-set applications to analysis in a real-time or near real-time situations, as would be the case for network flow monitoring, for example. As the complexity of a graph and the number of interactions or operational dependencies between graph nodes increase, the processing time and resources required to completely re-enumerate all cut-sets can render cut-set techniques infeasible in at least some applications.
In the context of network security analysis, or network analysis in general, actual network topology changes, and accordingly model changes, can be quite common. Complete re-enumeration of all cut-sets could severely limit the usability of a system based on cut-sets. Re-enumeration issues may similarly affect the use of cut-sets in other scenarios where the topology of a graph changes over time. For example, in the case of system reliability analysis, any change in an underlying system would affect the BDD and a re-enumeration of the cut-sets would be required, according to currently known techniques, in order to perform PRA.
Thus, there remains a need for improved graph-based modeling apparatus and techniques.